"""
求最大连续子数组的和
"""

def maxSubArray(A):
        # write code here
        if len(A) == 1:
            return sum(A)
        sum_A = []
        sum_ = 0
        for item in A:
            sum_ += item
            sum_A.append(sum_)

        def get_index(arr):
            min_ind = 0
            #先找到最小值索引
            for ind in range(len(arr)):
                if arr[ind] <= arr[min_ind]:
                    min_ind = ind
            #再从剩下区间找最大值索引
            max_ind = min_ind
            for ind in range(min_ind,len(arr)):
                if arr[ind] >= arr[max_ind]:
                    max_ind = ind
            return min_ind, max_ind
        min_index,max_index = get_index(sum_A)
        return sum(A[min_index+1:max_index+1])

array = [-2,0,-3,4,-2,2,2,-5,4]
c = [-2,2,-1,4]
print(maxSubArray(array) == 6)
print(maxSubArray(c) == 5)

